And thank you, the organisers, for inviting me
to speak here.
I'm honoured and humbled to speak among my
community and to speak alongside people whose works
I've been following since the beginning of my
academic journey.
So sincerely, thank you very much.
So I wanted to talk today about some
work that I've been doing on distance preserving
graph machine learning.
And before I start, let me just give
you a picture that will sort of motivate
the work that we were doing here.
So the idea that we were exploring is
that graphs have structural topology at all scales.
So you can think at the simplest level,
at the local scale, you have things like
local invariance, few hop neighbourhoods, even very small
things like scalars per node, like the degree
of each node.
And these fundamental invariance, they drive things like
decentralised consensus.
They drive things like message-passing convolutional neural
networks by doing these successive local aggregations.
Then if you go to the other end
of the spectrum, you have the global scale.
And you can think of, when I say
global scale here, I'm thinking of, I have
two nodes in my graph.
They're not necessarily connected.
How are they related throughout the graph?
So for instance, how many paths are there
between them?
Or perhaps more importantly, what is the shortest
path that I can take to get from
one node to another node?
And this is an important problem that drives
things like retrieval, routing, navigation, which are very
important problems in areas like robotics and operations
research.
And then somewhere in the middle, you have
the mesoscopic scale, which is sort of like
this middle scale between local and global.
And this scale is usually revealed in things
like multi-hop walks, effective resistance, as Antonio
Ortega said in the first plenary.
And this will reveal motifs, things like communities,
bottlenecks, and so on.
So the way I think about this is,
if I know that two nodes are connected
by an edge, they are sort of in
this local scale together.
If they're not connected by an edge, if
I ask myself, OK, are they in the
same community?
That's sort of like the mesoscopic scale.
Imagine they're not in the same community.
How far are they?
And this is what I think of as
the global scale.
So this is just some taxonomy for what
I mean when I'm referring to these different
scales.
And then the question that we were interested
in with my PhD student, Milet, by the
way, I should have said, this is in
collaboration with Shovik Dara from Georgia Tech and
Meher Chaitanya from KTH.
So what we were interested in understanding was,
can existing graph signal processing machine learning methods
embed this topology at all scales?
So when it comes to local embeddings, GNNs,
signal processing, do this beautifully.
This is beautifully handled by graph SP and
NML, at least in its traditional form.
Most graph signal networks are local.
So convolutions are defined by these weighted sums
of local aggregations.
And this is the case also with aggregation
message passing networks.
These are all just different names for the
same thing.
So this, I guess we can safely say
it's handled in particular by our community here.
But when it comes to the global and
the mesoscopic scale, there are some challenges.
So for instance, when it comes to finding
global embeddings, for instance, shortest path distances between
two nodes in a graph, this is difficult
to handle with local architectures like GNNs.
You would have to feel the number of
hops equal to the diameter, which is typically
not something that you want.
This can be handled in theory by graph
transformers, in particular dense, so-called dense graph
transformers, which are ones that allow every node
to attend to every other node, even without
an edge.
However, we know that this is not very
efficient because this dense attention scales as O
of N squared.
You have to fill this dense and by
end matrix.
And in particular, when thinking about the shortest
path problem, which is what we're gonna be
talking about in a second, if you were
to store all the shortest distance from a
node to all the other nodes in the
graph, that requires n-dimensional embeddings.
And so you can't, for instance, transfer this
architecture to a larger graph.
You have no size generalisation.
And moreover, I mean, you could say, okay,
I don't wanna find all shortest path distances.
I wanna find the top K, but the
top K won't match across nodes.
So you'll have this problem of the different
embedding dimensions are gonna correspond to different nodes,
and that's very bad for GNNs.
It really hurts generalisation.
Okay, so this is one area where both
GNNs and transformers struggle.
When it comes to mesoscopic embeddings, extracting these
mesoscopic embeddings, extracting this mesoscopic, right?
So we know that, for instance, if you
have well-behaved graphs, like dense graphs, you
can extract things like communities by using spectral
filters, spectral GNNs, of which convolutional filters and
GNNs are a type, right?
But they can be challenging to learn and
practise in some settings.
And for instance, I have, it's a little
bit small, but the second reference there on
the slide is a paper that we wrote
a few years ago for ICASP, where we
showed that GNNs are a little bit better
than spectral embeddings at finding communities in sparse
graphs, because they essentially, in sparse graphs, like
the top K eigenvectors are not as informative
as in dense graphs, right?
But what GNNs do well is they interpolate
the noise coming from the other eigenvectors.
However, the problem is that when you wanna
transfer that GNN to other graphs, even in
the same sort of random graph family, this
noise interpolation is not very transferable.
And so you have some challenges, right?
Even though this is feasible, you need large
enough receptive field, and there are some challenges
associated, for instance, with sparse graphs.
The idea here was to try to, in
order to try to address these issues, was
to try to preserve the appropriate metric for
each scale, right?
So when you talk about global scale, I've
been talking a lot about distances between nodes,
right?
And in particular, the shortest path distance is
a valid metric, right?
So what we will do here is I
will show you this class of algorithms that
I think has been studied for a good
while, and especially in these web conf community
and so on.
And these algorithms, what they do is they
try to, in a local step, learn some
sort of embedding, and then in a global
step, make sure that when you compute distances
between embeddings, they sort of replicate shortest path
distances.
And we will see that these are worst
case in nature, so they're a little conservative.
And so with me and my collaborator, Shavik
Dara, what we did was we analysed these
algorithms in homogeneous random graphs, which is a
much more realistic class of graphs, to try
to obtain sort of average case distortion guarantees.
So this is what we're gonna do first,
and then I'm also gonna show some empirical
results where we replace this local step that
I'll be more clear about in a few
moments with a GNN.
And this allows us to have things like
transferability, all the nice properties of GNNs.
So this will be the first part, and
then in the second part, we're going to
adjust the mesoscopic scale.
So here, what we're gonna do is we're
gonna use this type of embedding called the
maximum adjacency search embeddings.
These are inspired by cascades in opinion dynamics.
These are essentially the work of my other
collaborator, Meher, who's from this area.
And what these embeddings do is they count
occurrences of nodes in multi-hop.
What we will use these embeddings for is
to rewire the graph such that we are
capturing not just these local connections in the
graph, but also these maximally adjacent connections.
So there are nodes that might not be
connected by an edge, but they're in multiple
kind of multi-hop paths, and that means
they're maximally connected somehow.
And our goal will be to rewire the
graph, pass this graph through any architecture like
a GNN or a graph transformer, and hopefully
through this rewiring, be able to extract more
of this mesoscopic structure.
And here we'll see that the valid metric,
like the appropriate metric is the effective resistance,
and that we're able to lower bound the
effective resistance of these rewired edges that we
will add.
Okay, so let's start with the first part.
So the problem that we are trying to
address here is to approximate shortest path distances,
right?
This is sort of like a sub-problem
of the shortest path problem.
It's a little bit simpler.
You're not trying to find the shortest path.
You're just trying to find the shortest distance.
We know that one algorithm that you can
use to find shortest path problems in particular,
but the problem is that finding exact all
-pairs distances using this algorithm and even simplifications
of it is pretty prohibitive at scale, right?
So it scales as O of N times
N plus M, where N is the number
of nodes and M is the number of
edges in the graph.
And so one idea that has been explored
a lot by people working on this problem
is this idea of embedding nodes in some
space such that the distance between the embeddings
of the nodes in this space approximate the
graph distance, meaning the shortest path distance, okay?
And then the quality of these embeddings is
measured by a multiplicative distortion, right?
So if D hat here is the approximation,
we want it to be lower and upper
bounded like this.
We say that this approximation has one plus
minus epsilon distortion if it's lower bounded by
one minus epsilon, the actual shortest path distance,
and upper bounded by one plus epsilon, the
actual shortest path distance, okay?
Steps, a local step and a global step.
The local step is typically done offline.
So we do this step for all the
nodes in advance.
And the way it works is you sample,
so you're given your graph.
Here I'm just omitting the edges just to
make the image clearer.
But what you do is you sample landmark
sets, landmark sets, S0 through SR. And these
are sets of seed or landmark nodes.
So here I'm representing them by the orange
nodes.
And then what you do is you start
the distance of every node in the graph
to the nearest landmark per set, right?
So each node will have an r-dimensional
embedding where the jth entry of that embedding
is the minimum distance between you and an
element of that set, okay?
You do this offline for all nodes.
Typically the way people do this is doing
breadth-first search from the seeds or landmarks.
And then you store all these distances.
You get your node embeddings.
You can have the global step in a
query-based fashion, right?
So I can come to my server or
my computer and say, I want to approximate
the shortest path between U and V.
So the way you do this is you
look at these embeddings and you compute some
sort of approximation of the distance based on
the triangle inequality.
So there are two kind of classical ways
to do this.
The first way gives you a lower bound
for the actual shortest path distance, right?
So I'm writing the lower bound as the
underline.
And then here, I mean, the local step
is exactly as I described, right?
You're creating that embedding by distances from each
node to the closest seed in each one
of the sets.
And then in the global step, and this
is called Lugan's algorithm, what you do is
you use the inverse triangle inequality and you
obtain this lower bound, but essentially taking the
L infinity norm of the difference between the
embeddings.
So what this is doing in practise is
it's trying to find the maximum distance between
the embeddings coordinate-wise, right?
So that you're trying to find the set
that achieves this maximal distance.
And then there's another approach that was proposed
in this algorithm by, in this paper, by
Dasarma and others that gives you an upper
bound, right?
So it gives this D overline that upper
bounds the actual shortest path distance.
And here, seed nodes, what we also do
is we store the actual index of the
seed in SJ that achieves this distance, right?
So we want to know the size, you
know, like the size of the distance of
the node to each set, which is the
node in that sense that is closest to
you, okay?
So using these two sort of vectors, right?
One in our dimensional vector and the other
a scalar per node.
When we do the global step, we use
the triangle inequality, not the inverse, the reverse
triangle inequality now to upper bound the shortest
path distance by the minimum among the sum
between OXUJ and FXPJ such that the seeds
that achieve the minimum distance in the seed
set SJ match, right?
So this is what I have here, but
to approximate the distance between this U1 and
U2 here, I need to have a common
seed, right?
And so that's why you need this extra
embedding here.
What's wrong?
I'm sorry.
Yes, I'll stop moving.
Okay.
All right, so these two are classical algorithms.
And like I said, these algorithms don't mean
anything if they don't have distortion guarantees, right?
So we need a distortion guarantee both for
Bourgan's algorithm and the Sarma's algorithm.
Bourgan's algorithm gives us a lower bound.
And this theorem here, which is based on
Bourgan's embedding theorem, the lower bound distortion.
This theorem is actually, I mean, doesn't necessarily
apply just to the shortest from this very
important paper by Bourgan and then later by
Matuszek, where they essentially show the distortion of
embedding metric spaces into Hilbert spaces, right?
Because you always lose something when you do
that.
And this is basically that theorem applied to
this particular problem.
So what the theorem says is that, given
a large enough graph, for any constant C
that you fix, there exist optimal embeddings, which
are these X star embeddings that I have
here, with dimension at least N to the
one over C log N, such that the
lower bound estimator has bounded distortion, where the
distortion is given by that one over two
C minus one.
Okay?
So for instance, if you wanted to get
distortion of say, order, let's see here.
So if we do 1.5, this would
be half, right?
So you would get something like to the
one, like one over 1.5 log N
embeddings that gives you a distortion of one
half there.
Okay.
Then, besides having a distortion guarantee for the
lower bound, right?
So for Bourgan's algorithm, we also have distortion
guarantees for the upper bound from that more
recent paper.
And in that paper, besides proposing this algorithm,
they also provide guarantees whenever the seed sets
have size two to the J, okay?
With J ranging from zero to the floor
of log N.
And the reason why you need this construction
is one of the reasons is because, remember
that I said that you always need to
have this common seed.
You always need to have the common seed.
And so you always need to have at
least one set that has size one, right?
Because you might not find matching seeds in
the others.
You have to set S zero, give you
that triangle inequality approximation.
And what this theorem says is that you
get two C minus one distortion guarantee, right?
For the upper bound, for your upper bound
approximation of shortest path with embeddings X star
with dimension at least N to the one
over C log N.
Okay, so very similar.
Distortion guarantees.
And same minimum embedding dimension.
Now what is the issue with these distortion
results?
The issue with them is that they are
worst case in nature in the sense that
they hold even for, like imagine a graph
where approximating shortest paths is very hard.
For instance, a graph where you might have
like a nice sort of connected blob, but
you have these like very long paths, like
spider legs or something, right?
Approximating shortest paths in this graph is very
difficult if you don't sample a seed in
that path.
So these guarantees hold even in that case.
So you can imagine that they're pretty loose,
right?
And they are worst case.
And additionally, because these embedding sizes are not
small, this becomes prohibitive at scale.
And like I said, it's pessimistic for the
structured graphs that we actually have, right?
And actually what I did from the two
previous slides to this one is I just
expressed the minimum embedding dimension in terms of
epsilon, because now I wanna have one minus
epsilon, one plus epsilon distortion, so clean distortion.
And so I just adjusted the minimum embedding
size.
Okay, so what is your average case graph,
right?
Like what are graphs that are more realistic
and closer to what you have in practise?
One model that is very used to model
such graphs is the inhomogeneous random graph model.
And this model is basically an extension of
a stochastic block model.
So what happens is that in this model,
each node carries a type, right?
So each node belongs to sort of like
a type or a family, and the edge
probability will depend on the endpoint type.
So you'll have a matrix D, which is
called the affinity matrix that is sort of
encoding the affinity between nodes of different types.
And what you do is in order to
compute the probability of two nodes connecting in
this graph, you divide the corresponding entry of
D by the number of nodes in the
sort of the community of sort of like
your neighbour, right?
So D is not a probability, but when
you take the ratio of it with the
community size, your neighbour's community size, you get
a probability.
This model is very general, so it includes
things like the stochastic block model or the
Serenium when there's only one type.
And so our idea is to try to
derive those distortion guarantees now, not just for
these inhomogeneous random graphs that are a better
model of your typical graph that you encounter
in the real world.
So before I talk about our distortion results,
I just want to give you a sense
of the proof idea.
So like I said earlier, in these algorithms,
these local global algorithms, for sure there's a
path approximation, what you do is you effectively,
in order to compute the embeddings, you do
breadth-first search from the seeds, right?
Breadth-first search, you can think of it
as local exploration, right?
So I'm a node, I look at my
one-hop neighbours, then my two-hop neighbours,
and so on.
And as a sort of like a dynamical
process, you can think of this as a
branching process, right?
And in particular, if you have multiple types,
this will be a multi-type branching process
with mean matrix given by D, the affinity
matrix.
What you can show is that this branching
process, which is basically, I mean, this is
called a, it's sort of like a binomial
branching process, I think it's called the Galton
-Watson process, and basically, it's the process where,
each node when it branches out, it has
a number of sort of neighbours given by
the mean of the process, which in this
case here, if you have affinity matrix D,
that mean is going to be lambda one,
the formal eigenvalue of show.
Using this branching process approximation is that the
boundary of the k-hop neighbourhood of node
U is of order lambda one to the
k, right?
And what we further show, so after showing
these concentration of both the boundary size of
the k-hop neighbourhood, and also the size
of the entire k-hop neighbourhood, is you're
able to show that typical distances concentrate using
concentration of Bernoulli random variables.
Essentially, DUV, where DUV is the typical distance,
concentrates around log base lambda one of n,
okay?
And so this typical distance is what is
going to give us our distortion guarantee, and
concentration around it is what's gonna give us
our distortion guarantee.
So here is our result.
So using those two algorithms for the lower
bound and the upper bound, what we show
is that under bound regularity conditions on the
inhomogeneous random graph model, those landmark or seed
-based embeddings achieve one plus minus epsilon distortion
with high probability with embedding dimension, so for
the lower bound, at least n to the
one minus epsilon log lambda one n, and
then this more complicated expression for one plus
epsilon but in practise, I mean, if you
forget about this minimum here, you get something
like, it's like one, I think it's one
plus epsilon or something like that.
Yes, thank you.
Yes, so, right.
So the, much better, okay.
So there are a few interesting things to
notice here, right?
Like this doesn't look much better than the
embeddings that we had before, but they are
a little bit better.
So the first thing that you notice is
that this is governed now by the spectral
radius, lambda one of the affinity matrix, and
this eta n here is the minimum type
size exponent, right?
So this is sort of controlling for not
having very imbalanced types or communities, and what
you see is that more balanced types will
give you smaller embeddings, and that even though
this still doesn't look amazing, it's polynomially smaller
than those worst case, not distortion guarantees, the
worst case embedding sizes by approximately n to
the epsilon over two.
So there's a polynomial sort of gain that
you have here when you focus on homogenous
or non-graphs, right?
Like when you forget about worst case graphs.
So that was our main result.
Another thing that you can do is you
can extend this to the case of continuous
types.
So instead of having like a finite set
of types like in a stochastic block model,
you could have infinitely many types, for instance,
as in a graphon, right?
And so now your D is no longer
a matrix, it's a kernel, and this allows
you to extend these results to an even
larger set of graphs beyond SBM and Erdos
-Renyi, such as Chung-Liu graphs and others,
and the distortion bounds are very similar.
The way you extend that distortion result to
these graphs with infinitely many types is you
sort of sandwich the kernel, the continuous kernel,
by step function kernels and consider those step
function kernels to be graphs with finite types.
That was the sort of theoretical contribution to
derive these distortion guarantees for more realistic, more
average case graphs.
On the numerical side, what we did was
we replaced the breadth-first search step in
the local step of those algorithms with a
shortest path surrogate, right?
So it's just trained via imitation learning to
imitate breadth-first search or shortest path from
the seeds.
Even though these GNNs are not suited to
long shortest path computation, for short shortest paths,
they do reasonably enough.
And what we did was we trained on
small graphs, right?
We trained on a small 100-node and
homogeneous random graph.
This was an Erdos-Renyi random graph.
And then transferred to graphs up to 32
times larger.
And what we see here on this slide
is, so when your graphs are pretty sparse,
right?
So when the lambda is like three and
four, which is almost out of the supercritical
regime for Erdos-Renyi, what you see is
that breadth-first search always wins.
But once you get a little bit denser,
so your lambda is at five or six,
eventually you get better MSC with the GNNs
at a much lower cost, right?
So like you have to, this is for
the GNNs, so you have to make way
less calculations, especially for large graph sizes because
breadth-first search is exhaustive, right?
GNNs only go as far as k-hops,
l-layers.
Then we also did this experiment for real
-world networks, still using our GNNs trained on
those synthetic graphs.
And so what we did here was, again,
we transferred those GNNs to these real-world
graphs with order of 10,000 nodes.
And what we saw here was that, yes,
like for a given, starting from a certain
graph size, you get lower MSC when you
use GNNs to approximate the lower bound breadth
-first search.
And our main goal here was just to
see, do these inhomogeneous random graphs behave in
practise like your average real-world graph?
And given these results, we feel like they
must behave enough like these IHGs for the
theory to hold.
Okay, so this is the end of part
one.
I guess I can take questions now if
there are any questions before I move on
to part two.
So the question I saw here was how
to select the seed sets.
So in practise, you just sample them at
random, but it's an important problem, right?
And you can find smarter ways to do
it.
So for instance, I think the best way
to do it is to sample seeds with
high centrality, right?
Because they're gonna be not just very locally
connected, but very central in the graph.
Okay, so I'll move on.
So in the second part, like I mentioned
earlier, what we're gonna be doing is we're
going to try to rewire the graphs such
as to preserve or exploit the mesoscopic structure
a little bit better in signal processing and
machine learning pipelines.
And the reason for that is because both
GNNs and graph transformers can struggle at this
mesoscopic scale, right?
So graph neural networks or convolutional message-passing
GNNs, they aggregate over k-hop neighbourhoods where
I typically want k to be small.
So this receptive field is local.
And like I mentioned earlier, in some situations,
you might have a hard time accessing communities
and bottlenecks and that sort of thing.
People sometimes call this over-smoothing, over-squashing,
right?
And then when it comes to graph transformers
with dense attention, they have, they sort of,
I mean, if you're not gonna use the
graph structure, right, to compute your attention pairs,
you sort of lose that graph prior that
makes GNNs work so well.
And moreover, you have this O of N
squared attention that is very prohibitive for large
graphs.
At the same time, I've already motivated, right?
motivated, right, but like we we want in
some problems, in some problems the representations that
we want to learn or design, they, we
want them to reflect things like communities and
bottlenecks.
One thing that does that are multi-hop
walks, right?
So if you take multiple, say, random walks
of large enough length and you sort of
average statistics that you collect in these walks,
you're, in well-behaved graphs, you're able to
get, each rewire the graph by promoting these
pairs that are repeatedly showing up in the
same multi-hop walks.
So to do this, we're going to use
this idea of contagion dynamics from from opinion
dynamics and we're going to use two what
they call cascade rules for discovering this mesoscopic
structure, maximum adjacency search and threshold adjacency search.
So the way they work is they start
at a random seed.
Besides activating this random seed at step zero,
you also activate a random set of nodes
and then at each step what you're going
to do is you're going to activate the
inactive node with the most active neighbours in
maximum adjacency search.
You're going to be a bit more forgiving
with this activation and you're going to activate
any inactive node that has at least kappa
active neighbours.
These rules are just two different rules to
do the same thing, right?
Like they're both privileged, these multi-hop pairs
that are supported by short redundant paths, which
is this mesoscopic structure that we're trying to
to extract.
And so here I just have two videos
showing threshold cascade with two parameters kappa.
So here, it's a little fast, but you
can see I initialise at zero.
I also sample nodes four and three and
then I start looking at these maximally adjacent
adjacent nodes to zero, four, and three and
I do this repeatedly for a certain number
of steps.
This is for small thresholds who end up
activating a lot of nodes by the end.
So they end up activating 10 out of
60 nodes.
Here, if you increase the threshold a little
bit, activations are more rare.
Naturally, you're activating, eventually you're activating the one
-hop neighbours.
So you're not getting rid of this local
structure, but there's some selectivity in how you're
activating your further hop neighbours, right?
Your two-hop, three-hop neighbours and so
on.
So this selectivity is based on this maximal
adjacency idea.
Okay.
Another small thing here.
So we retain both, we also so the
graphs that we extract, these rewired graphs, they're
weighted.
So we symmetrise them and we weight them
by coactivation frequency.
So for instance, if I don't know, two
here shows up many multi-hop paths from
zero, right?
Like after doing this cascade for a number
of times, the weight is going to reflect
that that frequency of appearance.
And also these auxiliary graphs, they're not as
not super expensive to build, right?
Like they're, if m is order of n,
this is going to be O of n
to build.
And then the idea is to take these
auxiliary graphs and pass them as the backbone
to a GNN or a graph transformer.
So we have a couple of theoretical results
to sort of support this approach.
One is showing that rewiring helps when you
have graphs that are heterophilic.
So here, assume that you have that we
can write three events, right?
So the first one is label agreements, meaning
nodes have the same label in whatever task
you're trying to solve.
This will be calligraphic L, event calligraphic L.
Event calligraphic E will be that there's an
edge, not a directed edge, just an edge
between nodes U and V, meaning they're adjacent
in the graph.
And calligraphic R will mean that you have
reinforcement, meaning that there's at least kappa co
-occurrences of U and V in.
So given these events and given a random
unordered pair of distinct nodes U, V, we
define the standard edge homophily as the probability
that you have label agreement given that you
have an edge between U and V, and
the reinforcement homophily or the homophily in the
rewired graph as the probability that you have
label agreement given that you have reinforcement, or
in other words, given that you have adjacency
in the rewired graph.
And then what we were asking here was,
when is this homophily in the rewired graph
greater than homophily in the original graph?
The reason for this is because we know
that GNN's graph convolutions work well when you
have homophily, right?
So when similar nodes, not similar nodes, nodes
that are connected in the graph have similar
neighbours, similar labels, or for instance signals.
This is what Dirichlet energy measures, right?
More in our talking more in signal processing
terms.
So what we show in this proposition here
is that under two conditions.
So under the condition that we have sort
of heterophily in G, meaning that whenever the
labels between two nodes U and V agree,
you have a larger probability that they are
in the multi-hop path versus them being
direct neighbours.
And when the reinforcement event is less frequent
than edges, then the homophily of that rewired
graph is greater than the homophily of the
original graph.
And this is greater than or equal, but
it will be strict when these conditions are
strict.
And here we tried to illustrate this with
some synthetic and real-world graphs.
So what we did was we, the homophily
before and after rewiring, versus the log of
the original average degree and the sizes of
the balls here are indicating the homophily.
So small, like these dots, have low homophily.
The larger circles have high homophily.
And so what you see is that we
get the biggest increase in homophily right over
here when the original graphs are heterophilic and
when they have a high degree, right?
In some cases you, the homophily worsens, like
especially for very homophilic low degree graphs.
Okay, and then the other results that we
have, and this is a very simple result,
it's very related to what Antonio discussed on
Monday, the effective resistance of the edges in
the rewired graph, right?
So basically, I mean, what we're capturing once
we do this rewiring based on co-activation,
right, or nodes appearing in multiple multi-hop
paths, is we're encoding structural redundancy, right, in
the graph.
And basically what that structural redundancy means formally
is that, then what that means is that
G has K pairwise edge disjoint short paths
from the seed to U, right?
And this directly bounds the effective resistance I
probably don't need to define this again after
Antonio's talk, but it's basically just measuring sort
of like the voltage difference between two nodes,
right, based on the pseudo-inverse of the
Laplacian here, if you think that you have
a current source at U and a current
sink at V.
And the upper bound that we get for
this effective resistance in these rewired edges is
given by L, which is the length of
the kappa, where kappa is the activation threshold.
Right, so essentially here, it's not that we're
we're not preserving bottlenecks, right, because bottlenecks are
nodes with, are edges with high effective resistance.
We're preserving these redundant, so these pairs that
correspond to redundant, to redundancy in the graph.
We're preserving, we're connecting nodes with low effective
resistance.
Okay, so just a few numerical results before
I conclude.
So, and what we saw was, first of
all, it does relatively well.
So it's, in some data sets, it achieves,
like, the best performance.
In others, it does comparatively with using the
original graph, which is, which is nice.
But maybe the more interesting thing is the
alignment with the theory.
So we do see that the largest gains
occur for heterophilic graphs with a high degree.
When the assumptions of that first theorem on
the, on the improved homophily of the, of
the rewired graph don't hold, then we didn't
observe a lot of gains.
So this does seem to be more useful
for heterophilic graphs.
Although agnostics, so this is just GCN, right,
and these are three different graph transformer architectures.
All of these are sort of sparse graph
transformers where you don't have the graph structure,
but you sort of give the neighbours embeddings
as tokens.
So you can use the, this rewired graph
there.
These two here, we had pretty decent improvement.
And here, there's just, just more detail on
the improvement that we got on these heterophilic
data sets, right?
So especially for Chameleon and Cornell, the improvements
were, were pretty good.
Another best accuracy that we got on these
rewired graphs, on the label homophily, the log
average degree, and the connectivity of the, of
both the original and the rewired graph.
And what we saw is that, so M
-A-S-T-A-S here are our
methods, right?
So the values of the beta here, but
especially focussing on the R-squared, the adjusted
R-squared here for, you see that the
difference in, in, or the test accuracy, the
gains in test accuracy, are much better explained
by the structural properties of this rewired graph
in the original graph, right?
So there's improvements in, in homophily and this
change in effective resistance in the rewired graph
do seem to help performance.
Okay, so just to conclude, today I talked
about trying to preserve mesoscopic and global topology
in, in graphs.
For approximating global distances, we saw that landmark
embeddings are a good method, right?
That sort of still has that local step,
but then augments that with a, with a
global step.
And even though the distortion guarantees for these
algorithms is pretty bad in the worst case,
we see that on more average case graphs,
the distortion is.
We also saw that there's an interesting dependence
on the embedding dimension in the Peronic, and
that we can replace that breadth-first search
step in, in the local step with a
GNN surrogate that then allows us to sort
of leverage the nice properties of GNN such
as, as transferability.
And then in the second part, talking about
embedding or preserving mesoscopic structure, we use graph
cascades.
At these global mesoscopic scales, convolutions and attention
can be insufficient, right?
So one possible, I mean, there are many
approaches to these structures, right, to obtain embeddings
that embed these structures.
But the approach that we took here, and
the approach that I, I, I think is,
you know, I contend is a good approach,
is to make the use of the appropriate
metric, right, to try to preserve the appropriate
metric.
So in the global scale, the shortest path
metric, in the local, in the mesoscopic scale,
things like effective resistance, redundancy, and here we
try to do this in two ways.
So first, inside the ML model, right, so
trying to learn embeddings that, and in the
in trying to preserve mesoscopic scale, we did
so outside of the ML model via rewiring,
right, and existing ML and SP backbones.
Now for future direction, so related to what
Sergio asked, one thing that we can do
is we can do better seed or landmark
selection, right?
So typically this is done uniformly at random.
Our results rely on, but in practise you
could do better by using degree or centrality,
use even the cascade structure in these random
walks to select the landmarks.
Another direction that we're pursuing is extending those
shortest path embedding distortion guarantees to directed graphs,
which is a little bit more challenging because
now your matrix D is not symmetric and
you have to make sure you're respecting the
individual edges orientations.
Also perhaps doing some signal or feature-aware
cascade selection, right?
So we completely ignore the node features when
we're doing the cascade selection or the when
we're sort of computing those maximally adjacent node
pairs.
And then finally, because we're really focussing on
this rewiring method on nodes that have some
structural redundancy at the mesoscopic scale, the method
ends up not working well for graphs where
you have bottlenecks or for problems where the
bottlenecks are important.
So maybe combining this rewiring method with some
bottleneck targeted rewiring could give us better gains
at the mesoscopic scale and allow us to
cross narrower cuts.
Thank you, so these are the two papers
and thank you to my collaborators.
Thank you.
Johanna, thank you for the presentation.
Sorry if I missed this.
I'm curious about in the results, given that
graph transformers allegedly are naturally better for heterophilic
tasks, whether this like model agnostic improvement puts
GNNs on par to observe a difference.
Yeah, I don't think I have the raw
numbers, but transformers were doing better in practise.
Yeah, like majority of the time.
Also, we only tested GCN, I think.
GCN is not very good for these.
So yeah, that could also be an artefact.
I see.
Thank you.
I also have a question on part one.
Typically these real networks, they have always missing
edges.
They affect the shortest path search, etc.
What people sometimes do, they still embed them
in a hyperbolic space or any other space
and try to figure out there how to
find shortest paths.
Do you think that's possible now to extend
it?
Answer to is there a shortest path between
two disconnected nodes is no, there isn't.
Or like the shortest path has, the shortest
distance is infinity.
Right, so we do assume or because, so
when we do this branching process approximation, we
assume that we're in the supercritical regime and
there with high probability you have one giant
connected component.
So we leverage that, right?
It's important, yeah.
You talked about rewiring there as a way
to mitigate this and to investigate.
People also look extensively at virtual nodes.
Which would be instead of just rewiring on
the existing nodes, you have one extra node
and then you can do both rewiring or
new edges with that.
And I have a feeling that it will
really help in some of these aspects.
Yeah, so actually if I'm not mistaken this
VCR one, I think the V stands for
virtual.
So I think it's one of the graph
transformers that has this virtual edge.
So I mean we keep the virtual edge,
but we just add this rewiring, right?
And there are some decent improvements still.
So I guess, yeah, there's, it helps.
Because the virtual node, if you think about
it, it's sort of like adding this global
sort of node that's connecting everybody, right?
That's true, that's true, yes.